Corelab Seminar
2014-2015
Kyriakos Axiotis (NTUA)
Approximating Nash Equilibria and Dense Subgraphs via an
Approximate Version of Caratheodory’s Theorem
Abstract.
We present a recent paper of Siddharth Barman, introducing algorithmic applications of an approximate version of Caratheodory's theorem about convex hulls in R^d. Using this theorem Barman establishes an algorithm for computing ε-Nash equilibria for bimatrix games, parameterized by the sparsity of the payoff matrices. This yields a polynomial time approximation scheme for games with fixed column sparsity. The same theorem leads to an additive approximation algorithm for the normalized densest k-subgraph problem (parameterized by the maximum degree d) and also for the densest
k x k-bipartite subgraph problem.